package tree;
// 插入 删除 查找
// 二叉搜索树(TreeSet 和 TreeMap 的底层 key (不允许重复) )
public class BinarySearchTree {
    static class Node{
        public int key;
        public Node left;
        public Node right;

        public Node(int key) {
            this.key = key;
        }
    }

    public Node root;

    // 先来最简单的 查找
    // 找到 返回 节点
    // 找不到返回 null;
    public Node find(int key){
        if(root == null) return null;
        Node cur = root;
        while(cur != null){
            if(key > cur.key){
                cur = cur.right;
            }else if(key < cur.key){
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

    // 插入成功 true;
    // 存在 插入不成功 返回 false;
    public boolean insert(int key){
        if(root == null){
            root = new Node(key);
            return true;
        }
        // 找 元素可以插入的位置
        Node parent = null; // 当前节点的父亲节点
        Node cur = root;
        while(cur != null){
            if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }else if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }else {
                // 当前元素在树中存在
                return false;
            }
        }// 出循环 cur == null
        if(key > parent.key){
            parent.right = new Node(key);
        }else {
            parent.left = new Node(key);
        }
        return true;
    }

    // 删除
    // 要分情况讨论
    public boolean remove(int key){
        // 首先要找的要删除的位置 和 parent 的位置
        Node cur = root;
        Node parent = null;

        while(cur != null){
            if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }else if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }else {
                // 找到待删除元素 的位置和 他parent节点的位置
                remove(parent,cur);
                return true;
            }
        }
        return false;
    }

    private void remove(Node parent, Node cur) {
        if(cur.left == null){ // 情况 1 ： 待删除节点 没有左子树
            if(root == cur){ // a) 待删除元素是根节点
                root = root.right;
                return ;
            }
            if(parent.left == cur){ // 当前节点是 parent 的 左子树
                parent.left = cur.right;
            }else {// 当前节点是 parent 的 右子树
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if(cur == root){
                root = root.left;
                return ;
            }
            if(parent.left == cur){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {// 待删除的元素 左右子树都不为 null
            // 替罪🐏大法展示 ：
            // 从待删除节点的 左子树中找 最大值 （就是左子树的最右边） 或者 右子树的最小值 （就是右子树的最左边） 二者取其中一种就好
            // 将这个找到的节点把待删除节点的值进行覆盖
            // 删掉替罪羊
            Node goatParent = parent;
            Node deadGoat = cur;
            while(deadGoat.right != null){
                goatParent = deadGoat;
                deadGoat = deadGoat.right;
            }
            // deadGoat 出了这个循环 右子树 一定为 null

            cur.key = deadGoat.key;

            if(deadGoat == goatParent.left){
                goatParent.left = deadGoat.left;
            }else {
                goatParent.right = deadGoat.left;
            }
        }
    }

    public void preOrder(Node root){
        if(root == null) return ;
        System.out.print(root.key + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder(Node root){
        if(root == null) return ;
        inOrder(root.left);
        System.out.print(root.key + " ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(8);
        binarySearchTree.insert(3);
        binarySearchTree.insert(5);
        binarySearchTree.insert(7);
        binarySearchTree.insert(9);
        binarySearchTree.insert(6);
        binarySearchTree.remove(5);

        System.out.println();
        System.out.println("+++++++++++++++++++++");

        binarySearchTree.preOrder(binarySearchTree.root);
        System.out.println();
        System.out.println("+++++++++++++++++++++");

        binarySearchTree.inOrder(binarySearchTree.root);


//        binarySearchTree.preOrder(binarySearchTree.root);
//        System.out.println();
//        System.out.println("+++++++++++++++++++++");
//
//        binarySearchTree.inOrder(binarySearchTree.root);
//
//
//        binarySearchTree.remove(8);
//        System.out.println();
//        System.out.println("+++++++++++++++++++++");
//
//        binarySearchTree.preOrder(binarySearchTree.root);
//        System.out.println();
//        System.out.println("+++++++++++++++++++++");
//
//        binarySearchTree.inOrder(binarySearchTree.root);
//
//        binarySearchTree.insert(2);
//
//        System.out.println();
//        System.out.println("+++++++++++++++++++++");
//
//        binarySearchTree.preOrder(binarySearchTree.root);
//        System.out.println();
//        System.out.println("+++++++++++++++++++++");
//
//        binarySearchTree.inOrder(binarySearchTree.root);

    }

}
